package leetcode.pre50;

import java.util.Arrays;

/**
 * 实现 String.indexOf(str) 函数。
 * <p>
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 * <p>
 * 示例 1:
 * <p>
 * 输入: haystack = "hello", needle = "ll"
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: haystack = "aaaaa", needle = "bba"
 * 输出: -1
 *
 * @date 2020/5/31 17:41
 */
public class Code28_StringIndexOf_KMP_RK {
    public static void main(String[] args) {
        System.out.println("a".indexOf(""));
        String str1 = "aabaaabaaac";
        String str2 = "aabaaac";
        int[] next = getNext(str2.toCharArray());
        System.out.println(Arrays.toString(next));
        System.out.println(strStr2(str1, str2));
        System.out.println(strStr3(str1, str2));
    }

    /**
     * 方式1：暴力遍历，假设长串是M，短串是N，
     * 时间O((M-N)N)，最优O(M-N)
     */
    public static int strStr(String haystack, String needle) {
        if (haystack == null || needle == null
                || haystack.length() < needle.length()) return -1;
        if ("".equals(haystack) && "".equals(needle)) return 0;
        //如果len1 = 5, len2 = 2, 那么len1最后的其实位置是index = 3 = 5 - 2
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            boolean isSame = true;
            //从i开始匹配
            for (int j = i; j < i + needle.length(); j++) {
                if (haystack.charAt(j) != needle.charAt(j - i)) {
                    isSame = false;
                    break;
                }
            }
            if (isSame) return i;
        }

        return -1;
    }

    /**
     * 方式2：RK算法，时间O(M-N)，空间O(1)
     * 思路：s1,s2俩字符串，
     * 对s1中长为N的子串进行hash。s2也hash。
     * 1)若hash值等，有可能 子串和s2等
     * 2)若hash值不等，子串肯定不等
     * <p>
     * 计算s中子串hash，要用到前一个和后一个关系，(1)时间得到
     * <p>
     * 要考虑两个问题：
     * 1)大数问题，用取模计算
     * 2)char c 的取值范围为0~255，计算hash结果时会自动类型提升为int，
     * 为避免符号位扩展，使用 (unsigned int)c & 0x000000FF
     * <p>
     * hash算法：可以用等比求和，可以用数组存储hash值， 那么空间就是O(N)，也可以不存hash值
     * <p>
     * hash(n) = a^(n-1)*s1 + a^(n-2)*s2 + ...+ a*s(n-1)+ 1*sn
     * <p>
     * hash(i) = hash(i-1)*base - a^(i-2)*s1 + si
     */

    public static int strStr2(String haystack, String needle) {
        if (haystack == null || needle == null
                || haystack.length() < needle.length()) return -1;
        if (haystack.isEmpty() && needle.isEmpty()) return 0;
        //非空子串中，查询空串返回的是0
        if (needle.isEmpty()) return 0;

        //26个字符
        int base = 26;
        final long MOD = (long) Math.pow(2, 31);
        long hash1 = charToInt(haystack.charAt(0));
        long hash2 = charToInt(needle.charAt(0));
        int m = haystack.length();
        int n = needle.length();
        for (int i = 1; i < n; i++) {
            hash1 = (hash1 * base + charToInt(haystack.charAt(i))) % MOD;
            hash2 = (hash2 * base + charToInt(needle.charAt(i))) % MOD;
        }
        if (hash1 == hash2) return haystack.substring(0, n).equals(needle) ? 0 : -1;

        long al = 1; //base ^ n
        for (int i = 0; i < n; i++) {
            al = (al * base) % MOD;
        }

        int len = m - n;
        //0号对比不上，从1号开始对比
        for (int i = 1; i <= len; i++) {
            //先更新hash, 注意虽然al不可能越界，但是al * charToInt可能越界
            hash1 = (hash1 * base - al * charToInt(haystack.charAt(i - 1)) % MOD
                    + charToInt(haystack.charAt(n + i - 1))) % MOD;
            if (hash1 == hash2 && haystack.substring(i, n + i).equals(needle))
                return i;
        }
        return -1;
    }

    private static int charToInt(char c) {
        return c - '0';
    }

    /**
     * 方式3：KMP，分析见笔记基础班
     */
    public static int strStr3(String str1, String str2) {
        if (str1 == null || str2 == null
                || str1.length() < str2.length()) return -1;
        if (str1.isEmpty() && str2.isEmpty()) return 0;
        //非空子串中，查询空串返回的是0
        if (str2.isEmpty()) return 0;
        int[] next = getNext(str2.toCharArray());
        int i, j;
        for (i = 0, j = 0; i < str1.length() && j < str2.length(); ) {
            if (str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else if (j == 0) {// j == 0 && str1.at(0) != star2.at(0)
                i++;
            } else {// j > 0,
                j = next[j];
            }
        }
        return j == str2.length() ? i - j : -1;
    }

    public static int[] getNext(char[] c) {
        if (c == null || c.length == 0) return new int[0];
        if (c.length == 1) return new int[]{-1};
        int[] next = new int[c.length];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        for (int i = 2; i < next.length; ) {
            if (c[i - 1] == c[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                //cn = 0
                next[i++] = 0;
            }

        }
        return next;
    }


}
